// implementation of VertexSet class (that contains a set of vertices: this is used for the improved greedy search and interchangable vertices)
#include "VertexSet.h"
#include "Helpers.h"
#include "VertexDirectory.h"
#include <ctime>
using namespace std;

//-----------------------------------------------------------------------------------------
// Public
//-----------------------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// Ctor
// instantiate an empty set of vertices
//-----------------------------------------------------------------------------
VertexSet::VertexSet(VertexDirectory *dir)
{
	m_VertexDirectory = dir;
	m_Vertex1 = NULL;
	m_Vertex2 = NULL;
	m_IsReplacement = false;
	m_Interchangeable = false;
	
}

VertexSet::~VertexSet()
{

}

//-----------------------------------------------------------------------------
// Ctor
// instantiate set of vertices with a pair of vertices
//-----------------------------------------------------------------------------
VertexSet::VertexSet(pair<Vertex*, Vertex*> vertices)
{
	// if there are vertices in the set - add them to this instance
	if (vertices.first != NULL)
	{
		//m_Vertices.insert(vertices.first);
		m_Vertex1 = vertices.first;
		m_VertexDirectory = vertices.first->GetVertexDirectory();
	}
	else
	{
		m_Vertex1 = NULL;
	}
	if (vertices.second != NULL)
	{
		//m_Vertices.insert(vertices.second);
		m_Vertex2 = vertices.second;
		if (m_VertexDirectory == NULL)
		{
			m_VertexDirectory = vertices.second->GetVertexDirectory();
		}
	} else
	{
		m_Vertex2 = NULL;
	}
	m_IsReplacement = false;
	m_Interchangeable = false;
}

//-----------------------------------------------------------------------------
// Ctor
// instantiate set of vertices with 2 individual vertices 
//-----------------------------------------------------------------------------
VertexSet::VertexSet(Vertex *vertex1, Vertex *vertex2)
{
	m_Vertex1 = vertex1;
	m_Vertex2 = vertex2;
	m_VertexDirectory = vertex1->GetVertexDirectory();
	m_IsReplacement = false;
	m_Interchangeable = false;
}

//-----------------------------------------------------------------------------
// Neighbours
// returns true iff otherVertex is a neighbour of one of the vertices in this
// VertexSet
//-----------------------------------------------------------------------------
bool VertexSet::Neighbours(VertexBase* otherVertex)
{
	return (m_Vertex1->Neighbours(otherVertex) || m_Vertex2->Neighbours(otherVertex));
}

//-----------------------------------------------------------------------------
// Size
// returns the number of vertices in the VertexSet
//-----------------------------------------------------------------------------
int VertexSet::Size()
{
	int size  = 0;
	if (m_Vertex1 != NULL)
	{
		size++;
	}
	if (m_Vertex2 != NULL)
	{
		size++;
	}
	return size;
}

//-----------------------------------------------------------------------------
// IsInGraph - returns true iff both vertices in the pair are in the graph
//-----------------------------------------------------------------------------
bool VertexSet::IsInGraph()
{
	return m_Vertex1->IsInGraph() && m_Vertex2->IsInGraph();
}

//-----------------------------------------------------------------------------
// Vertex1
// returns the 1st vertex
//-----------------------------------------------------------------------------
Vertex *VertexSet::Vertex1()
{
	return m_Vertex1;
}

//-----------------------------------------------------------------------------
// Vertex2
// returns the 2nd vertex
//-----------------------------------------------------------------------------
Vertex *VertexSet::Vertex2()
{
	return m_Vertex2;
}

//-----------------------------------------------------------------------------
// Operator == : compares both vertices.
// This method compairs the object pointers. Returns true iff both vertex 
// pointers in otherVertexSet are contained in this object of vertex set
//-----------------------------------------------------------------------------
bool VertexSet::operator==(VertexSet &otherVertexSet)
{
	if (&otherVertexSet == this)
	{
		return true;
	}

	if ((otherVertexSet.Vertex1() != m_Vertex1) || (otherVertexSet.Vertex1() != m_Vertex2))
	{
		return false;
	}

	if ((otherVertexSet.Vertex2() != m_Vertex1) || (otherVertexSet.Vertex2() != m_Vertex2))
	{
		return false;
	}

	return true;
}

//-----------------------------------------------------------------------------
// Operator != : compares both vertices
// This method compairs the object pointers. Returns FALSE iff both vertex 
// pointers in otherVertexSet are contained in this object of vertex set
//-----------------------------------------------------------------------------
bool VertexSet::operator!=(VertexSet &otherVertexSet)
{
	return !((*this)==otherVertexSet);
}

//-----------------------------------------------------------------------------
// Name: returns set's name (pair of 2 names)
//-----------------------------------------------------------------------------
VertexSetKey VertexSet::Name()
{
	pair<VertexKey, VertexKey> res;
	if (m_Vertex1 != NULL)
	{
		res.first = m_Vertex1->Name();
	} else
	{
		res.first = VertexKey();
	}

	if (m_Vertex2 != NULL)
	{
		res.second = m_Vertex2->Name();
	} else
	{
		res.second = VertexKey();
	}
	
	return res;
}

//-----------------------------------------------------------------------------
// PrintName: printed version of name
//-----------------------------------------------------------------------------
string VertexSet::PrintName()
{
	string res = "(";
	if (m_Vertex1 != NULL)
	{
		res.append(m_Vertex1->PrintName());
	} else
	{
		res.append("NULL");
	}
	
	res.append(",");
	if (m_Vertex2 != NULL)
	{
		res.append(m_Vertex2->PrintName());
	} else
	{
		res.append("NULL");
	}

	res.append(")");
	return res;
}

//-----------------------------------------------------------------------------
// Copy
// copies vertexToCopy's data INTO this instance
//-----------------------------------------------------------------------------
void VertexSet::Copy(Vertex* vertex1ToCopy, Vertex *vertex2ToCopy)
{
	m_Vertex1->Copy(vertex1ToCopy);
	m_Vertex2->Copy(vertex2ToCopy);
}

//-----------------------------------------------------------------------------
// NeighboursInGraph
// return true if other vertex is a neighbour (in the graph) of one of the 
// vertices in this vertex set
//-----------------------------------------------------------------------------
bool VertexSet::NeighboursInGraph(VertexBase* otherVertex) 
{
	return (m_Vertex1->NeighboursInGraph(otherVertex) || m_Vertex2->NeighboursInGraph(otherVertex));
}

//-----------------------------------------------------------------------------
// NeighboursNotInGraph
// return true if other vertex is a neighbour (not in the graph) of one of the 
// vertices in this vertex set
//-----------------------------------------------------------------------------
bool VertexSet::NeighboursNotInGraph(VertexBase* otherVertex)
{ 
	return (m_Vertex1->NeighboursNotInGraph(otherVertex) || m_Vertex2->NeighboursNotInGraph(otherVertex));
}



//-----------------------------------------------------------------------------
//Interchangeable: returns true if this vertexSet is interchangeable or if one of the
// vertices in this set is contained in an interchangeable vertexset
//-----------------------------------------------------------------------------
bool VertexSet::Interchangeable()
{
	if (m_Interchangeable)
	{
		return true;
	}

	if (m_Vertex1 != NULL)
	{
		VertexSet *containingSet = m_Vertex1->GetContainingVertexSet();
		if (containingSet != NULL && containingSet != this)
		{
			if (containingSet->Interchangeable())
			{
				return true;
			}
		}
	}

	if (m_Vertex2 != NULL)
	{
		VertexSet *containingSet = m_Vertex2->GetContainingVertexSet();
		if (containingSet != NULL && containingSet != this)
		{
			if (containingSet->Interchangeable())
			{
				return true;
			}
		}
	}

	return false;
}

//-----------------------------------------------------------------------------
//IsReplacement: returns true if this vertexSet is a replacement or if one of the
// vertices in this set is contained in a replacement vertexset
//-----------------------------------------------------------------------------
bool VertexSet::IsReplacement()
{
		if (m_IsReplacement)
	{
		return true;
	}

	if (m_Vertex1 != NULL)
	{
		VertexSet *containingSet = m_Vertex1->GetContainingVertexSet();
		if (containingSet != this)
		{
			if (containingSet!= NULL && containingSet->IsReplacement())
			{
				return true;
			}
		}
	}

	if (m_Vertex2 != NULL)
	{
		VertexSet *containingSet = m_Vertex2->GetContainingVertexSet();
		if (containingSet != this)
		{
			if (containingSet!= NULL && containingSet->IsReplacement())
			{
				return true;
			}
		}
	}

	return false;
}

//-----------------------------------------------------------------------------
//GetReplacements: returns a set of possible replacement vertex sets for this
// vertex set object
//-----------------------------------------------------------------------------
set<VertexSetKey> VertexSet::GetReplacements()
{ 
	return m_Replacements;
}

//-----------------------------------------------------------------------------
//GetInterchangeables: returns a set of possible interchangeable vertex sets
// this vertex set can replace
//-----------------------------------------------------------------------------
set<VertexSetKey> VertexSet::GetInterchangeables() 
{
	return m_VerticesToReplace;
}

//-----------------------------------------------------------------------------
//SetInterchangeableFlag: sets interchangeable flag for this vertex set
//-----------------------------------------------------------------------------
void VertexSet::SetInterchangeableFlag(bool value)
{
	m_Interchangeable = value;
	m_Vertex1->SetInterchangeableFlag(value);
	m_Vertex2->SetInterchangeableFlag(value);
}

//-----------------------------------------------------------------------------
//SetReplacementFlag: sets flag for this vertex
//-----------------------------------------------------------------------------
void VertexSet::SetReplacementFlag(bool value)
{
	m_IsReplacement = value;
	m_Vertex1->SetReplacementFlag(value);
	m_Vertex2->SetReplacementFlag(value);
}

//-----------------------------------------------------------------------------------------
// SetInterchangeable: adds otherVertexSet to the set of replacements for this vertex set
// and update the vertices in the set to be interchangable
//-----------------------------------------------------------------------------------------
void VertexSet::SetInterchangeable(VertexBase* otherVertexSet, bool updateContainer) 
{
	VertexSet *vertexSet = dynamic_cast<VertexSet*>(otherVertexSet);
	if (m_Replacements.find(vertexSet->Name())==m_Replacements.end())
	{
		m_Replacements.insert(vertexSet->Name());
		// Only update flags for interchangeble vertices
		m_Vertex1->SetInterchangeable(NULL, updateContainer);
		m_Vertex2->SetInterchangeable(NULL, updateContainer);
		SetInterchangeableFlag(true);
		m_Vertex1->SetContaingVertexSet(this);
		m_Vertex2->SetContaingVertexSet(this);
	}
	
}

//-----------------------------------------------------------------------------------------
// ResetInterchangeableWithVertexSet: removes otherVertexset from the set of replacements
// for this vertex set
//-----------------------------------------------------------------------------------------
void VertexSet::ResetInterchangeableWithVertexSet(VertexSet* otherVertexSet) 
{
	if (!Interchangeable())
	{
		throw new GraphColoringException("Trying to remove a replacement from a non-interchangeable vertex set");
	}
	set<VertexSetKey>::iterator it;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		if (*it==otherVertexSet->Name())
		{
			m_Replacements.erase(it);
			return;
		}
	}

	// An interchangeable vertex set doesn't stop being one when it runs out of replacements, do not update flags!
}

//-----------------------------------------------------------------------------
// ResetInterchangeable - reset all replacements for this vertex set: removes
// all replacements from the replacement group and resets the flags 
// of the vertices in this set
//-----------------------------------------------------------------------------
void VertexSet::ResetInterchangeable() 
{
	m_Vertex1->ResetInterchangeable();
	m_Vertex2->ResetInterchangeable();
	m_VerticesToReplace.clear();
	SetInterchangeableFlag(false);
}

//-----------------------------------------------------------------------------------------
// SetAsReplacementFor: mark this vertex set as a possible replacement for otherVertex
// mark the vertices in this set as replacements.
//-----------------------------------------------------------------------------------------
void VertexSet::SetAsReplacementFor(VertexBase* otherVertexSet) 
{
	VertexSet *vertexSet = dynamic_cast<VertexSet*>(otherVertexSet);
	if (m_VerticesToReplace.find(vertexSet->Name()) == m_VerticesToReplace.end())
	{
		m_VerticesToReplace.insert(vertexSet->Name());	
		m_Vertex1->SetAsReplacementFor(NULL);
		m_Vertex2->SetAsReplacementFor(NULL);
		SetReplacementFlag(true);
		m_Vertex1->SetContaingVertexSet(this);
		m_Vertex2->SetContaingVertexSet(this);
	}
}

//-----------------------------------------------------------------------------------------
// ResetReplacementForVertex: 
// remove otherVertexSet from the set of vertex sets this object can replace
//-----------------------------------------------------------------------------------------
void VertexSet::ResetReplacementForVertexSet(VertexSet* otherVertexSet)
{
	if (!IsReplacement())
	{
		throw new GraphColoringException("Trying to reset replacement for a vertex set that isn't a replacement");
	}
	set<VertexSetKey>::iterator it;
	for (it = m_VerticesToReplace.begin(); it != m_VerticesToReplace.end(); it++)
	{
		if (*it == otherVertexSet->Name())
		{
			m_VerticesToReplace.erase(it);
			if (m_VerticesToReplace.empty())
			{
				// Clear all vertices' flags
				ResetIsReplacement();
			}
			return;
		}
	}	
}


//-----------------------------------------------------------------------------
// ResetIsReplacement - reset all vertex sets this vertex set could replace
// removes all sets from the verticesToReplace group and resets the flags 
// of the vertices in this set
//-----------------------------------------------------------------------------
void VertexSet::ResetIsReplacement() 
{
	if (!IsReplacement())
	{
		throw new GraphColoringException("Trying to reset replacement flags for vertex set that isn't a replacement");
	}

	if (m_IsReplacement)
	{
		ResetReplacementSet();
		return;
	}

	// Else - at least one containing vertex set is interchangeable, check both
	VertexSet *set1 = m_Vertex1->GetContainingVertexSet();
	if (set1 != NULL && set1->IsReplacement())
	{
		set1->ResetReplacementSet();
	}	
	

	VertexSet *set2 = m_Vertex2->GetContainingVertexSet();

	if (set2 != NULL && set2->IsReplacement())
	{
		set2->ResetReplacementSet();
	}
	
}


//-----------------------------------------------------------------------------------------
// CanBeReplaced: returns true if this vertex set is marked as iterchangeable, and has
// some valid replacement vertex set that can be added to the vertex set's original group
// (which means they can be switched) 
//-----------------------------------------------------------------------------------------
bool VertexSet::CanBeReplaced()
{
	if (!Interchangeable())
	{
		throw new GraphColoringException("Calling CanBeReplaced on non-interchangeable vertex set");
	}

	// If this vertex set is interchangeable, check it
	if (m_Interchangeable)
	{
		if (!CanInterchangeableVertexSetBeReplaced())
		{

			return false;
		}
	} else
	{
		// Else - at least one containing vertex set is interchangeable, check both
		VertexSet *set1 = m_Vertex1->GetContainingVertexSet();
		if (set1 != NULL)
		{
			if (set1->Interchangeable() && !set1->CanBeReplaced())
			{
				return false;
			}	
		}

		VertexSet *set2 = m_Vertex2->GetContainingVertexSet();

		if (set2 != NULL)
		{
			if (set2->Interchangeable() && !set2->CanBeReplaced())
			{
				return false;
			}	
		}
	}
	
	return true;
}

//-----------------------------------------------------------------------------
// CanReturnToOriginalGroup: returns true if we can return both vertices to 
// their original group
//-----------------------------------------------------------------------------
bool VertexSet::CanReturnToOriginalGroup()
{
	if (!Interchangeable())
	{
		throw new GraphColoringException("Calling CanBeReplaced on non-interchangeable vertex set");
	}

	if (m_Interchangeable)
	{
		return CanReturnToGroupForInterchangeable();
	} 

	// Else - at least one containing vertex set is interchangeable, check both
	VertexSet *set1 = m_Vertex1->GetContainingVertexSet();
	if (set1 != NULL && set1->Interchangeable())
	{
		if (!set1->CanReturnToGroupForInterchangeable())
		{
			return false;
		}
	}	
	

	VertexSet *set2 = m_Vertex2->GetContainingVertexSet();

	if (set2 != NULL && set2->Interchangeable())
	{
		if (!set2->CanReturnToGroupForInterchangeable())
		{
			return false;
		}
	}

	return true;
}

//-----------------------------------------------------------------------------------------
// CanBeRemovedFromReplacements: returns true if after removing this vertex set from the 
// replacements list for all the interchangeable vertex sets it belongs to, they can ALL
// still be replaced, or moved back to their original group
//-----------------------------------------------------------------------------------------
bool VertexSet::CanBeRemovedFromReplacements()
{
	if (!IsReplacement())
	{
		throw new GraphColoringException("Calling CanBeReplaced on non-interchangeable vertex set");
	}

	// If this vertex set is interchangeable, check it
	if (m_IsReplacement)
	{
		if (!CanReplacementVertexSetBeRemovedFromReplacements())
		{
			return false;
		}
	} else
	{
		// Else - at least one containing vertex set is interchangeable, check both
		VertexSet *set1 = m_Vertex1->GetContainingVertexSet();
		if (set1 != NULL)
		{
			if (set1->IsReplacement() && !set1->CanBeRemovedFromReplacements())
			{
				return false;
			}	
		}

		VertexSet *set2 = m_Vertex2->GetContainingVertexSet();

		if (set2 != NULL)
		{
			if (set2->IsReplacement() && !set2->CanBeRemovedFromReplacements())
			{
				return false;
			}	
		}
	}
	
	return true;
}

//-----------------------------------------------------------------------------------------
// UpdateReplacementState: Checks if this vertex set(marked as replacement)can still replace
// all the interchangeable vertex sets it belongs to
//-----------------------------------------------------------------------------------------
void VertexSet::UpdateReplacementState()
{
	if (!IsReplacement())
	{
		// If this vertex is not a replacement, stop now
		return;
	}
	
	set<VertexSetKey>::iterator it;
	set<VertexSetKey> verticesToReplaceCopy(m_VerticesToReplace);
	for (it = verticesToReplaceCopy.begin(); it!= verticesToReplaceCopy.end(); it++)
	{
		VertexSet *interchangeableVertexSet = VertexDirectory::GetVertexSet(*it);
		if (!interchangeableVertexSet->Interchangeable())
		{
			continue;
		}
		Group *group = dynamic_cast<Group*>(interchangeableVertexSet->Vertex1()->GetPreviousContainer());
		// If we can't add this vertex to the interchangeable one's original group
		if (!group->IsLegalToAdd(this))
		{
			interchangeableVertexSet->ResetInterchangeableWithVertexSet(this);
			this->ResetReplacementForVertexSet(interchangeableVertexSet);
			continue;
		}
		
	}
}

//-----------------------------------------------------------------------------------------
// UpdateReplacementStateForAllNeighboursInGraph: Goes over all of this vertex set's 
// neighbours in the graph and checks if they are still valid replacements. If not, removes
// them from all lists
//-----------------------------------------------------------------------------------------
void VertexSet::UpdateReplacementStateForAllNeighboursInGraph()
{
	set<VertexSet*>::iterator it;
	set<VertexSet*> neighbours = GetAllRelatedReplacements();
	for (it = neighbours.begin(); it != neighbours.end() ; it++)
	{
		VertexSet *vertexSet = *it;
		vertexSet->UpdateReplacementState();
	}
}

//-----------------------------------------------------------------------------
// CanAllNeighboursInterchangeablesBeReplaced : returns true if all the 
// interchangeables with replacements that are neighbours to this vertex can
// be replaced or returned to original group
//-----------------------------------------------------------------------------
bool VertexSet::CanAllRelatedInterchangeablesBeReplaced()
{

	set<VertexSet*> relatedInterchangeables = GetAllRelatedInterchangeables();
	return CanWholeListBeReplaced(relatedInterchangeables);
}

//-----------------------------------------------------------------------------
// HasNeighbourInGroup : returns true if one of the vertices has a neighbour
// in given group
//-----------------------------------------------------------------------------
bool VertexSet::HasNeighbourInGroup(Group *group) 
{ 
	return (m_Vertex1->HasNeighbourInGroup(group) || m_Vertex2->HasNeighbourInGroup(group));
}



//-----------------------------------------------------------------------------
// Replace : returns true if this vertex set is chosen to replace 
// replacedVertex
//-----------------------------------------------------------------------------
void VertexSet::Replace(Graph *graph) 
{
	if (!Interchangeable())
	{
		throw new GraphColoringException("Calling replace on non-interchangeable vertex set");
	}

	if (m_Interchangeable)
	{
		ReplaceInterchangeableSet(graph);
		return;
	}

	// Else - at least one containing vertex set is interchangeable, check both
	VertexSet *set1 = m_Vertex1->GetContainingVertexSet();
	if (set1 != NULL && set1->Interchangeable())
	{
		set1->ReplaceInterchangeableSet(graph);
	}	
	

	VertexSet *set2 = m_Vertex2->GetContainingVertexSet();

	if (set2 != NULL && set2->Interchangeable())
	{
		set2->ReplaceInterchangeableSet(graph);
	}
}

//-----------------------------------------------------------------------------
// ReturnToOriginalContainer : returns all vertices to their original group
//-----------------------------------------------------------------------------
void VertexSet::ReturnToOriginalContainer(bool updateFlags)
{
	if (!Interchangeable())
	{
		throw new GraphColoringException("Trying to return a vertex set that ins't interchangeable to original container");
	}
	m_Vertex1->ReturnToOriginalContainer(updateFlags);
	m_Vertex2->ReturnToOriginalContainer(updateFlags);
	if (updateFlags)
	{
		ResetInterchangeable();
	}
}

//-----------------------------------------------------------------------------
// RemoveAllReplacements : clears replacement list and removes the links
//-----------------------------------------------------------------------------
void VertexSet::RemoveAllReplacements() 
{
	if (!Interchangeable())
	{
		throw new GraphColoringException("Removing all replacments from non-interchangeable vertex set");
	}

	set<VertexSetKey>::iterator it;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		VertexSet *replacement = VertexDirectory::GetVertexSet(*it);
		replacement->ResetReplacementForVertexSet(this);
	}

	m_Replacements.clear();
}

//-----------------------------------------------------------------------------
// GetVerticesOriginalGroup : returns vertices original group
//-----------------------------------------------------------------------------
Group *VertexSet::GetVerticesOriginalGroup()
{
	if (!Interchangeable())
	{
		throw new GraphColoringException("Trying to get original group for non-interchangeable vertex set");
	}

	Group *group =  dynamic_cast<Group*>(m_Vertex1->GetPreviousContainer());
	if (group == NULL)
	{
		throw new GraphColoringException("Vertex from vertex set has no original group");
	}
	return group;
}

//-----------------------------------------------------------------------------
// GetContainingGraph : returns graph vertices belong to or NULL if none exists
//-----------------------------------------------------------------------------
Graph *VertexSet::GetContainingGraph()
{
	if (m_Vertex1 != NULL)
	{
		Graph *graph = m_Vertex1->GetContainingGraph();
		if (graph == NULL)
		{
			Graph *graph = m_Vertex2->GetContainingGraph();
			return graph;
		} else
		{
			return graph;
		}
	}
	else
	{
		return NULL;
	}
}


//-----------------------------------------------------------------------------
// GetPreviousContainer : 
// is used for interchangeable vertex sets. In this case the vertex set is 
// returned to the graph, nd this method will return the group the vertex setwas
// in when set as interchangable (it matches for both vertices)
//-----------------------------------------------------------------------------
VertexContainer* VertexSet::GetPreviousContainer()
{
	if (m_Vertex1 != NULL)
	{
		return m_Vertex1->GetPreviousContainer();
	}
	else
	{
		return NULL;
	}

}

//-----------------------------------------------------------------------------
// GetCurrentContainer :  Gets the container the set is currently in. assumes
// if vertex 1 is null, set is in no container
//-----------------------------------------------------------------------------
VertexContainer* VertexSet::GetCurrentContainer()
{
	if (m_Vertex1 != NULL)
	{
		return m_Vertex1->GetContainer();
	} else
	{
		return NULL;
	}
}


//-----------------------------------------------------------------------------
// ClearInterchangeableInformation :  Gets the container the set is currently in. assumes
// if vertex 1 is null, set is in no container
//-----------------------------------------------------------------------------
void VertexSet::ClearInterchangeableInformation()
{
	m_IsReplacement = false;
	m_Interchangeable = false;
	m_Replacements.clear();
	m_VerticesToReplace.clear();
	m_Vertex1->ClearInterchangeableInformation();
	m_Vertex2->ClearInterchangeableInformation();
}


//-----------------------------------------------------------------------------
// FindReplacements: Fills replacements from graph
//-----------------------------------------------------------------------------
void VertexSet::FindReplacements(Graph *graph)
{
	if (graph != NULL)
	{
		if (IsInGraph())
		{
			throw new GraphColoringException(PrintName()+ " is in graph, cannot find replacements");
		}
		graph->FindVertexSetReplacements(this);
	} else
	{
		Debug::PrintDebugMsg("Could not find graph for "+PrintName());
	}
}

//-----------------------------------------------------------------------------
// UpdateContainingSets : clears containing sets for this vertex set - sets
// flags to false
//-----------------------------------------------------------------------------
void VertexSet::ClearContainingSets()
{
	VertexSet *set1 = m_Vertex1->GetContainingVertexSet();
	if (set1 != NULL)
	{
		set1->SetInterchangeableFlag(false);
		set1->SetReplacementFlag(false);
		m_Vertex1->SetContaingVertexSet(NULL);
	}

	VertexSet *set2 = m_Vertex2->GetContainingVertexSet();
	if (set2 != NULL)
	{
		set2->SetInterchangeableFlag(false);
		set2->SetReplacementFlag(false);
		m_Vertex2->SetContaingVertexSet(NULL);
	}
}


//-----------------------------------------------------------------------------
// UndoReplacement : returns a replacement vertex set to the graph
//-----------------------------------------------------------------------------
void VertexSet::UndoReplacementWith(VertexSet *otherVertex, bool returnToGraph)
{
	Group *group = dynamic_cast<Group*>(m_Vertex1->GetContainer());
	if (group == NULL)
	{
		throw new GraphColoringException("Could not get interchangeable container from pointer");
	}

	Graph *graph = otherVertex->GetContainingGraph();

	group->RemoveVertexSet(this);
	if (returnToGraph)
	{
		graph->InsertVertexSet(this);
	} else
	{	
		m_Vertex1->ResetContainer();
		m_Vertex2->ResetContainer();
	}

	// Update flags
	otherVertex->SetInterchangeableFlag(true);
	SetReplacementFlag(true);	
}



//-----------------------------------------------------------------------------------------
// Private
//-----------------------------------------------------------------------------------------



//-----------------------------------------------------------------------------------------
// ReplaceWith: Replaces this vertexSet with replacementVertex
//-----------------------------------------------------------------------------------------
void VertexSet::ReplaceWith(VertexSet *replacementVertex,Graph *graph, bool updateFlags)
{
	if (!Interchangeable())
	{
		throw new GraphColoringException("Trying to replace a vertex set that isn't interchangeable");
	}

	if (graph == NULL)
	{
		throw new GraphColoringException("Replacing with NULL graph");
	}

	Group *group = GetVerticesOriginalGroup();
	if (group == NULL)
	{
		throw new GraphColoringException("Could not get interchangeable container from vertex 1 pointer");
	}

	if (replacementVertex->IsInGraph())
	{
		graph->RemoveVertexSet(replacementVertex);
		
	} else
	{
		Debug::PrintDebugMsg("replacement vertex set is not in graph");
	}

	group->InsertNewVertex(replacementVertex->Vertex1());
	group->InsertNewVertex(replacementVertex->Vertex2());

	if (updateFlags)
	{
		// Update all flags
		// The replacement is no longer a replacement, remove it from all lists
		replacementVertex->ResetIsReplacement();
		// This vertex is no longer interchangeable, remove it from all lists
		ResetInterchangeable();
	}
}



//-----------------------------------------------------------------------------------------
// GetLegalReplacementVertex: Gets the a legal replacement for this vertex set (or NULL if 
// none available)
//-----------------------------------------------------------------------------------------
VertexSet *VertexSet::GetLegalReplacementVertexSet()
{
	if (!Interchangeable())
	{
		throw new GraphColoringException("Getting replacement for non-interchangeable vertex set");
	}

	Group *group = GetVerticesOriginalGroup();
	if (group == NULL)
	{
		throw new GraphColoringException("Could not get interchangeable container from vertex 1 pointer");
	}

	int replacementCount = 0;
	set<VertexSetKey>::iterator it;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		VertexSet *replacement = VertexDirectory::GetVertexSet(*it);
		if (replacement->IsReplacement() && replacement->IsInGraph() && group->IsLegalToAdd(replacement, false))
		{
			replacementCount++;
		}
	}

	if (replacementCount == 0)
	{
		string message;
		message.append("Vertex Set has no legal replacement!");
		Debug::PrintDebugMsg(message);
		return NULL;
	}
	
	srand((unsigned)time(0));
	// Get a random index between 0 and max index (inclusive)
	long randomIndex = rand() % (replacementCount); 
	int counter = 0;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		VertexSet *replacement = VertexDirectory::GetVertexSet(*it);
		if (replacement->IsReplacement() && replacement->IsInGraph() && group->IsLegalToAdd(replacement, false))
		{
			if (counter == randomIndex)
			{
				return replacement;
			} else
			{
				counter++;	
			}	
		}
	}

	return NULL;
}

//-----------------------------------------------------------------------------------------
// GetAllRelatedInterchangeables: Returns a set of all vertex sets that can be replaced
// by neighbours to this vertex set
//-----------------------------------------------------------------------------------------
set<VertexSet*> VertexSet::GetAllRelatedInterchangeables()
{
	set<VertexSet*> result;
	AddInterchangeableVertexSetFromVertexNeighbours(m_Vertex1, &result);
	VertexSet* set1  = m_Vertex1->GetContainingVertexSet();
	if (set1 != NULL && set1 != this && set1->Interchangeable() && result.find(set1) == result.end())
	{
		result.insert(set1);
	}

	AddInterchangeableVertexSetFromVertexNeighbours(m_Vertex2, &result);
	VertexSet* set2  = m_Vertex2->GetContainingVertexSet();
	if (set2 != NULL && set2 != this && set2->Interchangeable() && result.find(set2) == result.end())
	{
		result.insert(set2);
	}


	return result;
}

//-----------------------------------------------------------------------------------------
// GetAllRelatedInterchangeables: Returns a set of all vertex sets that can be replaced
// by neighbours to this vertex set
//-----------------------------------------------------------------------------------------
set<VertexSet*> VertexSet::GetAllRelatedReplacements()
{
	set<VertexSet*> result;
	AddReplacementVertexSetFromVertexNeighbours(m_Vertex1, &result);
	VertexSet* set1  = m_Vertex1->GetContainingVertexSet();
	if (set1 != NULL && set1 != this && set1->IsReplacement() && result.find(set1) == result.end())
	{
		result.insert(set1);
	}

	AddReplacementVertexSetFromVertexNeighbours(m_Vertex2, &result);
	VertexSet* set2  = m_Vertex2->GetContainingVertexSet();
	if (set2 != NULL && set2 != this && set2->IsReplacement() && result.find(set2) == result.end())
	{
		result.insert(set2);
	}

	return result;
}

//-----------------------------------------------------------------------------------------
// GetAllRelatedInterchangeables: Returns a set of all vertex sets (out put parameter in 
// resultSet) that can be replaced by neighbours to this vertex
//-----------------------------------------------------------------------------------------
void  VertexSet::AddInterchangeableVertexSetFromVertexNeighbours(Vertex *vertex, set<VertexSet*> *resultSet)
{
	set<VertexKey>::iterator it;
	set<VertexKey> neighbours = vertex->GetNeighboursInGraph();
	for (it = neighbours.begin(); it != neighbours.end(); it++)
	{
		Vertex *neighbour = VertexDirectory::GetVertexFromDirectory(*it,m_VertexDirectory);
		// Get the neighbours containing vertex set 
		VertexSet *neighbouringSet = neighbour->GetContainingVertexSet();
		// If the vertex indeed belongs to a set and it is a replacement set
		if (neighbouringSet != NULL && neighbouringSet->IsReplacement())
		{
			set<VertexSetKey>::iterator interIt;
			set<VertexSetKey> interchangeables = neighbouringSet->GetInterchangeables();
			for (interIt = interchangeables.begin(); interIt != interchangeables.end(); interIt++)
			{
				VertexSet *relatedInterchangeable = VertexDirectory::GetVertexSet(*interIt);
				// Add interchangeable vertex if it is not this one or in use and isn't in the set already
				if (relatedInterchangeable != this && relatedInterchangeable->Interchangeable() && resultSet->find(relatedInterchangeable)== resultSet->end())
				{
					resultSet->insert(relatedInterchangeable);
				}
			}
		}

		if (neighbouringSet != NULL && neighbouringSet->Interchangeable())
		{
				if (neighbouringSet != this && resultSet->find(neighbouringSet)== resultSet->end())
				{
					resultSet->insert(neighbouringSet);
				}
		}
	}
}

//-----------------------------------------------------------------------------------------
// AddReplacementVertexSetFromVertexNeighbours: Returns a set of all vertex sets (out put parameter in 
// resultSet) that are neighbours to this vertex and are replacements
//-----------------------------------------------------------------------------------------
void  VertexSet::AddReplacementVertexSetFromVertexNeighbours(Vertex *vertex, set<VertexSet*> *resultSet)
{
	set<VertexKey>::iterator it;
	set<VertexKey> neighbours = vertex->GetNeighboursInGraph();
	for (it = neighbours.begin(); it != neighbours.end(); it++)
	{
		Vertex *neighbour = VertexDirectory::GetVertexFromDirectory(*it,m_VertexDirectory);
		// Get the neighbours containing vertex set 
		VertexSet *neighbouringSet = neighbour->GetContainingVertexSet();
		// If the vertex indeed belongs to a set and it is a replacement set
		if (neighbouringSet != NULL && neighbouringSet->IsReplacement() && resultSet->find(neighbouringSet) == resultSet->end())
		{
			resultSet->insert(neighbouringSet);
		}
	}
}


//-----------------------------------------------------------------------------------------
// CanWholeListBeReplaced: Returns true if whole list of interchangeable vertex sets can 
// be replaced or returned to original groups
//-----------------------------------------------------------------------------------------
bool VertexSet::CanWholeListBeReplaced(set<VertexSet*> interchangeables)
{
	if (interchangeables.empty())
	{
		return true;
	}

	// Get and remove front element
	VertexSet *currentInterchangeable = *(interchangeables.begin());
	interchangeables.erase(interchangeables.begin());

	bool replace = false;
	bool returnToGroup = false;
	VertexSet *set1 = m_Vertex1->GetContainingVertexSet();
	VertexSet *set2 = m_Vertex2->GetContainingVertexSet();


	// if this interchangeable is a containing set, we can't return it to the group and have to replace it
	if (currentInterchangeable != set1 && currentInterchangeable != set2 && currentInterchangeable->CanReturnToOriginalGroup())
	{
		Debug::PrintDebugMsg(currentInterchangeable->PrintName() + " is not containing and can return to group");		returnToGroup = true;
	}

	if (!returnToGroup && currentInterchangeable->CanBeReplaced())
	{
		Debug::PrintDebugMsg(currentInterchangeable->PrintName()+ " can be replaced in whole list...");
		replace = true;
	}

	bool canBeReplaced =  returnToGroup || replace;

	if (canBeReplaced)
	{
		VertexSet *replacement;
		Graph *graph = currentInterchangeable->GetContainingGraph();
		bool replacementInGraph;
		if (returnToGroup)
		{
			graph->RemoveVertexSet(currentInterchangeable);
			// Return vertex to original group but do not erase all lists
			currentInterchangeable->ReturnToOriginalContainer(false);
		} else
		{
			replacement = currentInterchangeable->GetLegalReplacementVertexSet();
			if (replacement == NULL)
			{
				return false;
			}
			replacementInGraph = replacement->IsInGraph();
			if (replacementInGraph)
			{
				// try to replace this vertex
				currentInterchangeable->ReplaceWith(replacement,graph, false);
			} else
			{
				Debug::PrintDebugMsg("replacement chosen is not in graph");
				return false;
			}
		}
		canBeReplaced = CanWholeListBeReplaced(interchangeables);

		// Clean up
		// If we retuned the vertex to the group, put in back in the graph
		if (returnToGroup)
		{
			Group *group = dynamic_cast<Group*>(currentInterchangeable->GetPreviousContainer());
			if (group == NULL)
			{
				throw new GraphColoringException("Interchangeable has no original group");
			}
			group->RemoveVertexSet(currentInterchangeable);
			graph->InsertVertexSet(currentInterchangeable);
			currentInterchangeable->SetInterchangeableFlag(true);
		} else
		{
			// Undo replacement
			replacement->UndoReplacementWith(currentInterchangeable, replacementInGraph);
		}
	}

	return canBeReplaced;
}


//-----------------------------------------------------------------------------------------
// CanInterchangeableVertexSetBeReplaced: Returns true this vertex set (really interchangeable)
// can be replaced
//-----------------------------------------------------------------------------------------
bool VertexSet::CanInterchangeableVertexSetBeReplaced()
{
	if (!m_Interchangeable)
	{
		throw new GraphColoringException("Calling CanInterchangeableVertexSetBeReplaced on a vertexset that isn't marked interchangeable");
	}

	// Assuming this is correct - this container is the copy one
	Group *group = GetVerticesOriginalGroup();
	if (group == NULL)
	{
		throw new GraphColoringException("Interchangeable container is not a group!");
	}

	// Check if there is a replacement vertex that works as a replacement
	set<VertexSetKey>::iterator it;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		// Try to replace and see that all interchangeables are still OK
		VertexSet *replacement = VertexDirectory::GetVertexSet(*it);
		if (!replacement->IsReplacement())
		{
			continue;
		}
		
		if (!group->IsLegalToAdd(replacement, false))
		{
			continue;
		}

		if (!replacement->IsInGraph())
		{
			continue;
		}

		// See what happens after replacing
		ReplaceWith(replacement, replacement->GetContainingGraph(), false);
		
		bool interchangeablesState = replacement->CanAllRelatedInterchangeablesBeReplaced();

		replacement->UndoReplacementWith(this, true);

		// If this is a combination that works, this vertex can be replaced
		if (interchangeablesState = true)
		{
			Debug::PrintDebugMsg(this->PrintName() + " can be replaced by " + replacement->PrintName());
			return true;
		}
	}
	Debug::PrintDebugMsg(this->PrintName() + " cannot be replaced");
	return false;
}

//-----------------------------------------------------------------------------------------
// CanReplacementVertexSetBeRemovedFromReplacements: internal can replacement be removed from
// replacements check (for real replacement listed in directory)
//-----------------------------------------------------------------------------------------
bool VertexSet::CanReplacementVertexSetBeRemovedFromReplacements()
{
	if (!m_IsReplacement)
	{
		throw new GraphColoringException("Calling CanBeRemovedFromReplacements on non-replacement vertex set");
	}

	// Stop being a replacement
	SetReplacementFlag(false);

	set<VertexSetKey>::iterator it;
	for (it = m_VerticesToReplace.begin(); it != m_VerticesToReplace.end(); it++)
	{
		bool legal = true;
		VertexSet *interchangeableVertexSet = VertexDirectory::GetVertexSet(*it);
		if (!interchangeableVertexSet->Interchangeable())
		{
			continue;
		}

		// Remove this vertex from interchangeableVertex's list and check it can still be replaced
		if (!interchangeableVertexSet->CanReturnToOriginalGroup() && !interchangeableVertexSet->CanBeReplaced())
		{
			legal = false;
		}
		if (!legal)
		{
			// Return this vertex to replacement lists
			SetReplacementFlag(true);
			return false;
		}
	}
	// Return this vertex to replacement lists
	SetReplacementFlag(true);
	return true;
}

//-----------------------------------------------------------------------------
// ReplaceInterchangeableSet : replaces set
//-----------------------------------------------------------------------------
void VertexSet::ReplaceInterchangeableSet(Graph *graph)
{
	if (!m_Interchangeable)
	{
		throw new GraphColoringException("Trying to replace a non-interchangeable vertex set");
	}

	string message = "Replacing ";
	message.append(this->PrintName());
	Debug::PrintDebugMsg(message);


	VertexSet *replacement = GetLegalReplacementVertexSet();
	if (replacement == NULL)
	{
		throw new GraphColoringException("No replacement available for vertex set");
	}
	

	ReplaceWith(replacement, graph, true);
}

//-----------------------------------------------------------------------------
// ResetReplacementSet : resets replacement flags
//-----------------------------------------------------------------------------
void VertexSet::ResetReplacementSet()
{
	if (!m_IsReplacement)
	{
		throw new GraphColoringException("Calling reset replacement on non-replacement set");
	}

	string message = "Removing ";
	message.append(this->PrintName());
	message.append(" from replacements");
	Debug::PrintDebugMsg(message);


	m_Vertex1->ResetIsReplacement();
	m_Vertex2->ResetIsReplacement();
	set<VertexSetKey>::iterator it;
	for (it = m_VerticesToReplace.begin(); it != m_VerticesToReplace.end(); it++)
	{
		VertexSet *vertexSet = VertexDirectory::GetVertexSet(*it);
		if (vertexSet->Interchangeable())
		{
			vertexSet->ResetInterchangeableWithVertexSet(this);
		}
	}
	SetReplacementFlag(false);
}


//-----------------------------------------------------------------------------
// CanReturnToGroupForInterchangeable : checks if this specific vertex set
// can return to original group
//-----------------------------------------------------------------------------
bool VertexSet::CanReturnToGroupForInterchangeable()
{
	if (!m_Interchangeable)
	{
		throw new GraphColoringException("Calling CanBeReplaced on non-interchangeable vertex set");
	}
	
	if (!m_Vertex1->IsInGraph() || !m_Vertex2->IsInGraph())
	{
		return false;	
	}

	// Assuming this is correct - this container is the copy one and both vertices have same container
	Group *group = dynamic_cast<Group*>(m_Vertex1->GetPreviousContainer());
	
	SetInterchangeableFlag(false);
	bool canReturn = group->IsLegalToAdd(this, true);
	SetInterchangeableFlag(true);

	return canReturn;
}

